//338 Counting Bits
/*
给定一个非负整数 n，求从 0 到 n 的所有数字的二进制表达中，分别有多少个 1

输入输出样例：
	输入是一个非负整数 n，输出是长度为 n + 1 的非负整数数组，每个位置 m 表示 m 的二进制里有多少个 1

Input: 5
Output: [0,1,1,2,1,2]

*/
vector<int> countBits(int num) {
	vector<int> dp(num + 1, 0);
	for (int i = 1; i <= num; ++i)
		dp[i] = i & 1 ? dp[i - 1] + 1 : dp[i >> 1];
	// 等价于dp[i] = dp[i&(i-1)] + 1;
	return dp;
}

//268
//693
//476
//260

